package leetcode_800;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *NetworkDelayTime_743 寻找最短路径
 *describe:迪杰斯特拉算法解决 AC 7%
 *2018年10月14日 下午8:25:10
 */
public class NetworkDelayTime_743 {
	 public int networkDelayTime(int[][] times, int N, int K) {
	        HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();  // Create a graph + record time
	        for(int i = 0; i < times.length; i++){
	            map.putIfAbsent(times[i][0], new HashMap<>()); 
	            map.get(times[i][0]).putIfAbsent(times[i][1], times[i][2]); 
	        }
	 
	        int[] visit = new int[N + 1]; 
	        for(int i = 1; i < visit.length; i++){ // Record shortest time from start node to current node, Integer.MAX_VALUE means not visited. 
	            visit[i] = Integer.MAX_VALUE; 
	        }
	        
	        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); 
	        //定义堆的排序策略 
	        pq.add(new int[]{K, 0}); 
	        while(!pq.isEmpty()){
	            int[] cur = pq.poll(); 
	            int node = cur[0]; 
	            int len = cur[1]; 
	            visit[node] = Math.min(visit[node], len); 
	            if(map.containsKey(node)){
	                for(Integer neighbor : map.get(node).keySet()){
	                    if(visit[neighbor] == Integer.MAX_VALUE){
	                        int newLen = visit[node] + map.get(node).get(neighbor); // Through previous shorted record to get new len
	                        pq.add(new int[]{neighbor, newLen}); 
	                    }
	                }
	            }           
	        } 
	        
	        int max = -1; 
	        for(int i = 1; i < visit.length; i++){//保存最短路径
	            if(visit[i] == Integer.MAX_VALUE){ // Never visit this node
	                return -1; 
	            }else{
	                max = Math.max(max, visit[i]); 
	            }
	        }
	        return max; 
	        
	    }
}
